Packing Ellipses Using Embedded Lagrange Multipliers

Frank J. Kampas
Frank @ Physicistatlarge.com

Abstract

Ellipses are packed into a circumscribing circle using Lagrange multipliers for finding the points on the ellipses most distant from the origin and the points on pairs of ellipses closest to each other.

Introduction

Packing ellipses into a circumscribing circle is more complex than packing circles, since there are no symbolic equations for the maximum distance from the center of the circumscribing circle to an ellipse and for the minimum distance between two ellipses.  This problem is overcome by embedding into the optimization problem constraints containing Lagrange multipliers for determining the point on each ellipse most distant from the origin and the points on all pairs of ellipses closest to each other.

Formulation

Mathematical Description of the Ellipses

eleq is the equation of an ellipse of the form (((x/a))^2)+ (((y/b))^2) - 1 == 0 , first rotated counterclockwise by an angle θ and then having its center shifted to {xc, yc}.  To speed up calculations, cos(θ) is used in the formula as cosθ , going  from -1 to 1 with 0 being no rotation and sin(θ) is calculated from it.  The value of eleq is 0 for points on the ellipse and greater than 0 for points outside it.  This will be used, in conjunction with equations to find points on pairs of ellipses closest to each other, to prevent the ellipses from overlapping.

eleq[{a_,b_,xc_,yc_,cosθ_}][{x_,y_}]= (((((x/a))^2)+(((y/b))^2)-1 )/. {x -> cosθ*x +(Sqrt[ 1-((cosθ)^2)])y, y -> -(Sqrt[ 1-((cosθ)^2)])*x + cosθ*y})/. {x -> x - xc, y -> y-yc}

Find the Point on the Ellipse Most Distant From the Origin

The Lagrangian for maximizing or minimizing (x^2)+ (y^2) for a point lying on the ellipse is given by the following equation.  λ is negative for the point furthest from the center of the circumscribing circle.  This will be enforced by setting bounds on it in the optimization.

lagm[{a_,b_,xc_,yc_,cosθ_}][{x_,y_,λ_}]= (x^2)+(y^2) + λ*eleq[{a,b,xc,yc,cosθ}][{x,y}]

Lagrange’s equations for maximizing (x^2)+ (y^2) for a point lying on the ellipse are calculating by setting the derivatives of the Lagrangian with respect to x, y and λ equal to 0.

lagmeqns[{a_,b_,xc_,yc_,cosθ_}][{x_,y_,λ_}] = Thread[D[lagm[{a,b,xc,yc,cosθ}][{x,y,λ}],{{x,y,λ}}]==0]

Find the Closest Points on Pairs of Ellipses

The Lagrangian for minimizing the distance between a point of one ellipse and a point on another ellipse is as follows.  Variable names ending in 1 refer to first ellipse and variable names ending in 2 refer to the second ellipse.

lagc[{a1_,b1_,xc1_,yc1_,cosθ1_}][{a2_,b2_,xc2_,yc2_,cosθ2_}][{x1_,y1_,λ1_}][{x2_,y2_,λ2_}]= (((x2-x1))^2)+(((y2-y1))^2) + λ1*eleq[{a1,b1,xc1,yc1,cosθ1}][{x1,y1}] + λ2*eleq[{a2,b2,xc2,yc2,cosθ2}][{x2,y2}]

The corresponding Lagrange’s equations

lagceqns[{a1_,b1_,xc1_,yc1_,cosθ1_}][{a2_,b2_,xc2_,yc2_,cosθ2_}][{x1_,y1_,λ1_}][{x2_,y2_,λ2_}]= Thread[D[lagc[{a1,b1,xc1,yc1,cosθ1}][{a2,b2,xc2,yc2,cosθ2}][{x1,y1,λ1}][{x2,y2,λ2}],{{x1,y1,λ1,x2,y2,λ2}}]==0]

Packing

Initial Positions and Orientations of the Ellipses to be Packed

The i after xc, yc and cosθ refer to initial position and orientation.

elvals1={a[1],b[1],xci[1],yci[1],cosθi[1]} = {1.25,1.5,2,2,Cos[(π/3)]};
elvals2={a[2],b[2],xci[2],yci[2],cosθi[2]} = {1.5,1.25,0,-2,Cos[2 (π/3)]};
elvals3={a[3],b[3],xci[3],yci[3],cosθi[3]} = {0.75,1.33,-1.75,1,Cos[((4π)/3)]};

el1 = eleq[elvals1][{x,y}];
el2 = eleq[elvals2][{x,y}];
el3 = eleq[elvals3][{x,y}];

{p1,p2,p3} = ContourPlot[(#==1),{x,-5,5},{y,-5,5}]& /@ {el1,el2,el3};

Show[p1,p2,p3]

Set Up

Number of Ellipses:

nel = 3;

Bounds on variables

lb = -5.;ub = 5.;

The solution variables for the ellipses (p following xc, yc, and cosθ refer to the packed values)l

elvals[i_]:= {a[i],b[i],xcp[i],ycp[i],cosθp[i]}

Lagrange’s equations for the points on ellipse i furthest from the origin (m following x and y indicate the maximum values)

lagmi[i_]:= lagmeqns[elvals[i]][{xm[i],ym[i],λ[i]}]

Lagrange’s equations for finding the closest points on ellipses i and j.  { x[ i, j ], y[ i, j ] } is the position of the point on ellipse i closest to ellipse j.

lagcij[i_,j_]:= lagceqns[elvals[i]][elvals[j]][{x[i,j],y[i,j],λ[i,j]}][{x[j,i],y[j,i],λ[j,i]}]

Equations for preventing the ellipses from overlapping are set up by noting the value of eleq for ellipse i, evaluated for the closest point on ellipse j, is greater than 0 if the ellipses do not overlap.

disj[i_,j_]:=eleq[elvals[i]][{x[j,i],y[j,i]}]≥  0.01

Construction of the Variables, Objective Function and Constraints

obj = circrad;

The square of circrad, the radius of the circumscribing circle, is constrained to be >=  the square of the furthest distance from the origin to each ellipse.

cons = Flatten @ 
{
Table[(circrad^2)≥ ((xm[i])^2)+((ym[i])^2),{i,nel}],
Table[lagmi[i],{i,nel}],
Table[lagcij[i,j],{i,nel-1},{j,i+1,nel}],
Table[disj[i,j],{i,nel-1},{j,i+1,nel}]
};

Variables, their lower bounds, initial values, and upper bounds. Note that the Lagrange multipliers, λ[i] for the points on ellipse i furthest from the origin have ranges less than zero and the Lagrange multipliers λ[i, j] for closest points for pairs of ellipses have positive ranges.

vwbi =
Join[
 {{circrad,0,ub/2,ub}},
Table[{xcp[i],lb,xci[i],ub},{i,nel}],
Table[{ycp[i],lb,yci[i],ub},{i,nel}],
Table[{cosθp[i],-1.,cosθi[i],1.},{i,nel}],
Table[{xm[i],lb,1.5*xci[i],ub},{i,nel}],
Table[{ym[i],lb,1.5*yci[i],ub},{i,nel}],
Table[{λ[i],lb,lb/2,0},{i,nel}],
Flatten [Table[{x[i,j],lb,0,ub},{i,nel-1},{j,i+1,nel}],1],
Flatten[Table[{x[j,i],lb,0,ub},{i,nel-1},{j,i+1,nel}],1],
Flatten [Table[{y[i,j],lb,0,ub},{i,nel-1},{j,i+1,nel}],1],
Flatten[Table[{y[j,i],lb,0,ub},{i,nel-1},{j,i+1,nel}],1],
Flatten[Table[{λ[i,j],0,ub/2,ub},{i,nel-1},{j,i+1,nel}],1],
Flatten[Table[{λ[j,i],0,ub/2,ub},{i,nel-1},{j,i+1,nel}],1]
];

The number of constraints

Dimensions[cons]

The number of variables

Dimensions[vwbi]

Solve Using MathOptimizer Professional

Needs["MathOptimizerProLF`callLGO`"]

packslnm=callLGO[obj,cons,vwbi, LGOMethod -> "LocalSearch"]

packslnm2 = packslnm[[2]];

{p1p,p2p,p3p} = {
ContourPlot[(eleq[{a[1],b[1],xcp[1],ycp[1],cosθp[1]}][{x,y}]/. packslnm2)==0,{x,-3,3},{y,-3,3}],
ContourPlot[(eleq[{a[2],b[2],xcp[2],ycp[2],cosθp[2]}][{x,y}]/. packslnm2)==0 ,{x,-3,3},{y,-3,3}],
ContourPlot[(eleq[{a[3],b[3],xcp[3],ycp[3],cosθp[3]}][{x,y}]/. packslnm2)==0,{x,-3,3},{y,-3,3}]
};

pts are the points on the ellipses closest to each other.

pts = Graphics @ {PointSize[0.015],Table[Point[{x[i,j],y[i,j]}],{i,nel},{j,Complement[Range[nel],{i}]}]}/. packslnm2;

ptsm are the points on the ellipses furthest from the center of the circumscribing circle

ptsm = Graphics @ {PointSize[0.015],Table[Point[{xm[i],ym[i]}],{i,nel}]/. packslnm2};

circ is the circumscribing circle

circ = Graphics @ Circle[{0,0},circrad]/. packslnm2;

Show[p1p,p2p,p3p,circ,pts,ptsm, ImageSize -> Medium]

Conclusion

Ellipse packing can be performed using embedded Lagrange multipliers to determine the points on the ellipses most distant from the origin and points on pairs of ellipses closest to each other.